This invention relates to automatic reclamation of allocated, but unused memory, or garbage, in a computer system that uses a generational garbage collector and to methods and apparatus for reducing overhead resulting from object pre-tenuring decisions. Modern programming languages like the Java™ programming language or C# allow the use of automatic memory reclamation, or “garbage collection”, which relieves programmers of the burden of explicitly freeing, or de-allocating, storage allocated to objects when the objects are no longer used, or reachable, by the application program. Memory reclamation may be carried out by a special-purpose garbage collection algorithm that “collects” memory by locating and identifying as free, dynamically assigned memory (called “heap” memory) that is unused, but has not been explicitly de-allocated. There are many known garbage collection algorithms, including reference counting, mark-sweep, mark-compact and generational garbage collection algorithms. These, and other garbage collection techniques, are described in detail in a book entitled “Garbage Collection, Algorithms for Automatic Dynamic Memory Management” by Richard Jones and Raphael Lins, John Wiley & Sons, 1996.
However, many of the aforementioned garbage collection techniques often lead to long and unpredictable delays because normal application thread processing must be suspended during the garbage collection process and these collectors at least occasionally scan the entire heap memory. For example, many modern applications have large live data sets, sometimes measured in gigabytes. Even on fast modern processors, collecting the entire heap in one atomic operation can take several seconds. Some applications require only minimizing the total garbage collection overhead and may be able to tolerate such delays. Other applications, such as real-time or interactive systems, where non-disruptive behavior is of greatest importance generally cannot use techniques which collect the entire heap in one operation and, thus, cause considerable disruption.
One conventional technique that has been used to reduce these delays is the use of generational garbage collectors that provide performance benefits over non-generational garbage collectors. Generational garbage collectors assume that applications observe a “weak generational” hypothesis, which is that most newly-allocated objects quickly become unreachable or “die”. These garbage collectors take advantage of this hypothesis by concentrating garbage collections in an area of the memory heap, called the “young generation,” in which all new objects are allocated. Such collections, called “minor” collections, are usually fast because the young generation is typically quite small and most objects in it are expected to be dead. Objects that survive a few minor collections are “promoted” or copied to an area of heap memory called an “old” generation. The old generation is eventually collected by “major” collections, which are typically slower because the old generation is typically larger than the young one. However, since most collections occur in the young generation, the overall delay introduced by garbage collection is reduced.
Pre-tenuring is a technique that identifies objects which are expected to be long-lived and allocates these directly into the old generation heap area. This direct allocation avoids the cost of copying the objects from the young generation to the old generation if the objects are later promoted. In garbage collectors that perform collections by copying objects out of the collected area, called “copying garbage collectors”, pre-tenuring also avoids copying the objects during every minor collection.
A decision to pre-tenure an object is generally made at each allocation site for that object. Such an allocation site is a point in the application program code where the object is instantiated, thereby allocating memory space for the object. It is generally known that a particular allocation site tends to allocate objects of similar lifetimes. Thus, several known pre-tenuring methods dynamically decide at which allocation sites objects will be pre-tenured by performing some form of sampling on the allocated objects (at different granularities and using different techniques). The program code at such allocation sites is then modified to allocate the objects directly into the old generation.
One of the disadvantages of all the sampling techniques used by known pre-tenuring techniques is that they impose a small, but non-trivial, constant throughput overhead on the application. The least intrusive conventional techniques typically impose an overhead ranging between three and five percent and, in some applications, such an overhead is wasteful.